#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 297. 二叉树的序列化与反序列化.py
@time: 2022/2/18 17:17
@desc: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
> 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

@解题思路：
    1. 先序遍历
    2. Ot(n), Os(n)
'''


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        self.res = ''

        def travel(root):
            if not root: self.res += 'None,'; return
            self.res += str(root.val) + ','
            travel(root.left)
            travel(root.right)

        travel(root)
        # 去掉最后一个逗号
        self.res = self.res[:-1]
        return self.res

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        def redeser():
            if self.tree_list[0] == 'None':
                self.tree_list = self.tree_list[1:]
                return None
            root = TreeNode(int(self.tree_list[0]))
            self.tree_list = self.tree_list[1:]
            root.left = redeser()
            root.right = redeser()
            return root
        self.tree_list = data.split(',')
        return redeser()

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

if __name__ == '__main__':
    root = TreeNode(1, left=TreeNode(2), right=TreeNode(3, left=TreeNode(4), right=TreeNode(5)))
    ser = Codec()
    deser = Codec()
    ans = deser.deserialize(ser.serialize(root))
    print(ans)